#include<iostream>
#include<vector>

using namespace std;

//floodfill01：图像渲染
class Solution1 {
public:
    int dirs[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
    int a=0;
    int b=0;
    int init=0;
    //bool check[50][50]={};
    //bool** check=nullptr;
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) 
    {
        a=image.size();
        b=image[0].size();
        //bool tmp[a][b]={};
        //check=tmp;
        init=image[sr][sc];
        if(init==color) return image;
        dfs(image,sr,sc,color);
        return image;
    }
    void dfs(vector<vector<int>>& image, int sr, int sc, int color)
    {
        //cout<<sr<<":"<<sc<<" ";
        image[sr][sc]=color;

        for(auto& it:dirs)
        {
            int x=sr+it[0];
            int y=sc+it[1];
            if(x>=0&&x<a&&y>=0&&y<b&&image[x][y]==init)
            {
                //check[x][y]=true;
                dfs(image,x,y,color);
            }
                
        }
    }
};

//floodfill02:岛屿数量
class Solution2 {
    //bool check[300][300]={};
    vector<vector<bool>> check;
    int m=0;
    int n=0;
    int dirs[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
    int ret=0;
public:
    int numIslands(vector<vector<char>>& grid) 
    {
        m=grid.size();
        n=grid[0].size();
        check=vector<vector<bool>>(m,vector<bool>(n));
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(grid[i][j]=='1'&&check[i][j]==false)
                {
                    dfs(grid,i,j);
                    ret++;
                }
            }
        }
        return ret;
    }
    void dfs(vector<vector<char>>& grid,int i,int j)
    {
        //cout<<i<<":"<<j<<" ";
        check[i][j]=true;
        for(auto& it:dirs)
        {
            int x=i+it[0];int y=j+it[1];
            if(x>=0&&x<m&&y>=0&&y<n&&grid[x][y]=='1'&&check[x][y]==false)
                dfs(grid,x,y);
        }
    }
};



int main()
{
    return 0;
}